#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int N = 2e5+10;

int n,bl[N],a[N],b[N],bn,tot,pot[N],ans[N],BL,m,cnt,fst[N],lst[N];
struct query{
	int l,r,id;
	bool operator < (const query b){return bl[l] ^ bl[b.l] ? bl[l] < bl[b.l] : r < b.r;}
}q[N];

int calc(int l,int r){
	static int pos[N]; int res = 0;for(int i = l;i <= r;i++) pos[a[i]] = 0;
	for(int i = l;i <= r;i++){
		if(!pos[a[i]]) pos[a[i]] = i;
		else res = max(res,i - pos[a[i]]);
	}return res;
}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in; BL = sqrt(n); for(int i = 1;i <= n;i++) bl[i] = (i - 1) / BL + 1,a[i] = in,b[i] = a[i]; bn = bl[n];
	sort(b+1,b+n+1); tot = unique(b+1,b+n+1) - b - 1;
	m = in;
	for(int i = 1;i <= m;i++){q[i].l = in,q[i].r = in; q[i].id = i;}
	for(int i = 1;i <= n;i++) a[i] = lower_bound(b+1,b+n+1,a[i]) - b - 1;
	sort(q+1,q+m+1);
	for(int i = 1,j = 1;j <= bn;j++){
		int br = min(n,j * BL),l = br+1,r = l-1,tot = 0;
		cnt = 0;
		for(;bl[q[i].l] == j;i++){
			if(bl[q[i].r] == j) ans[q[i].id] = calc(q[i].l,q[i].r);
			else{
				while(r < q[i].r){
					r++; lst[a[r]] = r; if(!fst[a[r]]) fst[a[r]] = r,pot[++cnt] = a[r];
					else tot = max(tot,r-fst[a[r]]);
				}
				int lt = tot;
				while(l > q[i].l){
					l--; if(!lst[a[l]]) lst[a[l]] = l,pot[++cnt] = a[l];
					else tot = max(tot,lst[a[l]] - l);
				}
				ans[q[i].id] = tot;
				while(l <= br){
					if(lst[a[l]] == l) lst[a[l]] = 0;
					l++;
				}
				tot = lt;
			}
		}
		for(int k = 1;k <= cnt;k++) fst[pot[k]] = lst[pot[k]] = 0;
	}
	for(int i = 1;i <= m;i++) printf("%d\n",ans[i]);
	return 0;
}

